package com.bee.剑指offer;

import java.util.ArrayDeque;
import java.util.HashMap;
import java.util.Map;
import java.util.Queue;

/**
 * 请实现一个函数用来找出字符流中第一个只出现一次的字符。
 * 例如，当从字符流中只读出前两个字符 "go" 时，第一个只出现一次的字符是 "g" 。
 * 当从该字符流中读出前六个字符 “google" 时，第一个只出现一次的字符是"l"。
 */
public class 字符流中第一个不重复的字符 {

    Map<Character, Integer> map = new HashMap<>();

    int[] num = new int[300];

    Queue<Character> queue = new ArrayDeque<>();

    /**
     * 使用队列和数组是实现
     * 队列，用来存储元素，顺序
     * 数组：用来保存元素的出现次数
     * map:也可以，key为字符，value为出现的次数
     */
    public void Insert(char ch) {
//        if(!map.containsKey(ch)) {
//            map.put(ch,1);
//            queue.offer(ch);
//        } else if(map.get(ch) == 1) {
//            map.put(ch,-1);
//        }
        if (num[ch] == 0) {
            num[ch] = 1;
            queue.offer(ch);
        } else if (num[ch] == 1) {
            num[ch] = -1;
        }
    }

    public char FirstAppearingOnce() {
//        while (!queue.isEmpty() && map.get(queue.peek()) == -1) {
//            // 说明出现了多次，移除
//            queue.poll();
//        }
//        if(!queue.isEmpty()) {
//            return queue.peek();
//        }
        while (!queue.isEmpty() && num[queue.peek()] == -1) {
            queue.poll();
        }
        if (!queue.isEmpty()) {
            return queue.peek();
        }
        return '#';
    }

    public static void main(String[] args) {

    }
}
